//
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <time.h>
#include <stdlib.h>


void HeapSort(int*A,int n);
void BuildMaxHeap(int *A,int n);
void Swap(int &x, int &y);
void MaxHeapify(int *a,int left,int right);

int random_in_range (unsigned int min, unsigned int max)
{
  //Randomize
	int base_random = rand(); /* in [0, RAND_MAX] */
	if (RAND_MAX == base_random) return random_in_range(min, max);
  /* now guaranteed to be in [0, RAND_MAX) */
	int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;
  /* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void RandomGenerate(int *&a, int n)
{
	a = new int[n];
	for(int i = 0; i < n; i++)
	{
		a[i] = random_in_range(1, 100);
	}
}

void PrintfArray(int *a, int n)
{
	for(int i = 0; i < n; i++)
	{
		printf("  %d", a[i]);

	}
	printf("\n");
}


void HeapSort(int*a,int n)
{
	BuildMaxHeap(a,n);//khoi tao heap ban dau
	int r=n-1;//r la phan tu cuoi cung
	while(r>0)
	{
		Swap(a[0],a[r]);//hoan vi phan tu dau va phan tu cuoi
		r--;//bo qua ptu cuoi (khong xet nua)
		if(r>0)
			MaxHeapify(a,0,r);//tai' tao lai danh sach thanh` ->heap
	}
}
void BuildMaxHeap(int *a,int n)
{
	int i;//xac dinh i -><i la phan tu cuc phai cua doan ben trai
	if(n%2==0)
		i=n/2-1;//VD: n-8 -> i=3(ben trai co chi so la 0,1,2,3; ben phai la 4,5,6,7)
	else
		i= (n-1)/2;//VD: n=9 -> i=4(ben trai co chi so la 0,1,2,3,4; ben phai la 5,6,7,8)
	while(i>=0)
	{
		MaxHeapify(a,i,n-1);//xu li lan truyen
		i--;
	}
}
void Swap(int &x, int &y)//hoan vi
{
	int z=x;
	x=y;
	y=z;
}
void MaxHeapify(int *a,int left,int right)
{
	int x,i,j;
	i=left;
	j=2*i;
	x=a[i];//kiem tra DK;Co can xu li lan truyen nua k.(xem sile PP de hieu)
	while(j<=right)
	{
		if(j<right)//xet xem co ton tai phan tu A[j+1] ko?
		{
			if(a[j]<a[j+1])//j la chi so cua ptu co gia tri lon nhat trong 2 ptu A[j] va A[j+1]
				j++;
		}
		if(x>=a[j])//neu thoa dk cua heap thi thoi, return
			return;
		else
		{
			//neu khong thoa dk cua heap thi hoan vi A[i] voi A[j]
			a[i]=a[j];
			a[j]=x;
			//xac dinh cac ptu can xu ly lan truyen tiep theo
			i=j;
			j=2*i;
			x=a[i];
		}

	}
}

void main()
{
	int n;//n la so phan tu mang
	int *a;// khai bao con tro mang

	n = 50000;
	RandomGenerate(a,n);
	//PrintfArray(a,n);

	clock_t start = clock();
	HeapSort(a,n);
	printf("\nTime elapsed: %f\n\n", ((double)clock() - start) / CLOCKS_PER_SEC);

	
	//PrintfArray(a,n);

	getch();
}


/*/
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <time.h>
#define Max 100

void Exchange(int &a, int &b);

int random_in_range (unsigned int min, unsigned int max)
{
  //Randomize
	int base_random = rand(); // in [0, RAND_MAX] //
	if (RAND_MAX == base_random) return random_in_range(min, max);
  // now guaranteed to be in [0, RAND_MAX) 
	int range       = max - min,
      remainder   = RAND_MAX % range,
      bucket      = RAND_MAX / range;
  // There are range buckets, plus one smaller interval
  //   within remainder of RAND_MAX 
  if (base_random < RAND_MAX - remainder) {
    return min + base_random/bucket;
  } else {
    return random_in_range (min, max);
  }
}

void RandomGenerate(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		a[i] = random_in_range(1, 100);
	}
}

void PrintArray(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		printf("  %d", a[i]);
	}
	printf("\n");
}

void MaxHeapify(int a[], int n, int i)
{
	int l = 2*i;
	int r = 2*i + 1;
	int largest=0;
	if(l<=n && a[l]>a[i])
	{
		largest = l;
	}
	else
	{
		int largest = i;
	}

	if(r<=n && a[r]>a[largest])
	{
		largest = r;
	}
	if(largest != i)
	{
		Exchange(a[i],a[largest]);
		MaxHeapify(a,n,largest);
	}

}
void BuildMaxHeap(int a[], int n)
{
	for(int i = n/2; i>=1; i--)
	{
		MaxHeapify(a,n,i);
	}
}

void Exchange(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void HeapSort(int a[], int n)
{
	BuildMaxHeap(a,n);
	for(int i=n; i>=2; i--)
	{
		Exchange(a[1],a[i]);
		MaxHeapify(a,i-1,1);
	}
};


int main()
{
	int a[Max];
	int n;

	n = 15;
	RandomGenerate(a,n);
	PrintArray(a,n);
	//HeapSort(a,n);
	//PrintArray(a,n);


	getch();
	return 0;
}
/*/
